P2P systems are presently successful at a commercial level and are normally included in devices such as, for example, Set Top Boxes. P2P applications, both of a file-sharing and of a streaming nature, rely on infrastructure developed by several users organized in an overlay network. Although the Internet Protocol supports multicast distribution (i.e. data distribution to a group of IP addresses), P2P systems create the network and manage the content distribution, at application layer. The overlay can be created and managed in ways dependent on the nature of the application. In general, contents are split in chunks and then re-assembled at client side in the right order.
In the case of “file sharing,” a whole file is downloaded and then played offline, without constraints in terms of bandwidth or time delay. “Video on demand” streaming instead starts playback while the file is being downloaded, dealing with bandwidth and time constraints. The same is true for “live streaming”, where however peers are not usually sharing the whole content (it is not available yet) but just a small buffer of data close to the content production and playback time.
This disclosure will focus on file-sharing, although the proposed features may apply in general also to streaming applications. The protocol known as BitTorrent is adapted to share files more rapidly as compared to traditional P2P programs. BitTorrent is a program which was developed as open source; therefore, many different versions of the program are available, having the same protocol specification and the same basic code that can be used to share files.
With the architecture schematically represented in FIG. 1, which shows a so-called “swarm” of peer terminals P1, P2, . . . , Pn in a P2P network, each user, through the information contained in a small file with .torrent extension, can access a tracker T1, i.e. simply a server that ensures communication among the several peers. Tracker T1 is the critical element in the communication, because the peers themselves must start downloading. Moreover, the peers who have already started downloading periodically contact the tracker T1, in order to negotiate the bits exchange with the new peers who may have joined the network and in order to perform the diffusion of statistic information indicative of the traffic features and of the trustiness of the above mentioned peers. In any case, after the initial reception of a bit of file data, the peer can continue the communication and the exchange with or without the tracker T1. The tracker T1 may also be comprised by the web server W1, wherein the list of available Torrent files is stored. For the end user, it is sufficient to click the file he/she wants to download. W1 and T1 are, from the point of view of functionality, two separate entities which are adapted respectively, to show the list of downloadable files and to host the Torrent files (W1), and to download the information of the swarm peers (T1) However, they may often coincide and reside in one web server W1, where both the torrent file list and the tracker T1 reside.
First of all, the peer looks up, from the web interface of W1, the list of available Torrent files, so it chooses the Torrent. This Torrent file is obviously not the actual file that the user wishes to download, but, rather, is a small sized file indicating which of all the other terminals in the network have the file available. Once the Torrent file has been downloaded and run by the P2P program (adapted to the BitTorrent version available on the user's terminal), the tracker T1 is contacted in order to download the list of users belonging to the swarm and to start downloading.
In this respect, BitTorrent distinguishes between two different types of peers. In particular, a “seed” is a peer that has a complete copy of the file to be distributed. On the contrary, a “leecher” is a user or terminal that has bits of it. With BitTorrent, users allow the upload of the file that they are currently downloading from other users. A user will finish downloading a certain bit of a full file, and will automatically send it out to other users. In detail, a file is made up of bits (sometimes named chunks) comprising 16 KB blocks. Each peer notifies the possession of one bit, and sends single 16 KB blocks of the chunk when the peer requests them. The peer requests blocks and notifies the possession of chunks.
BitTorrent offers the advantage not to require these pieces or bits to be downloaded in sequence. The possible appearance of bottlenecks in bandwidth is a problem that on the contrary affects other programs, such as Bearshare. This means that most users of a traditional P2P program do nothing but downloading: when a file is shared, many different users may try to be loading the same file at the same time, and this creates a bottleneck in bandwidth, because there is a lot of traffic trying to get to the same file simultaneously from one source.
BitTorrent requires little bandwidth from the initial source of the file to be distributed: once the small Torrent file has been made available, the peers using BitTorrent are pointed to all the seeds and the peers that can provide file chunks, and perform their work by sharing every individual bit of information they have downloaded. This swarm technique in FIG. 1 allows multiple parallel downloads, because different chunks of the file can be simultaneously downloaded from different clients. When a terminal has completed the download, it informs all peers to which it is connected through a HAVE message, so that they can automatically upload it.
The BitTorrent program currently follows two basic rules. First, a user's BitTorrent sends data to peers that have previously sent data to it, creating a give and receive relationship. Second, the peer limits the number of uploads to four, and continuously looks for the best four peers from which to download.
This process is implemented with a “choke/unchoke” policy. Choking is when a terminal temporarily refuses to let another peer upload a content. However, the user's connection is not closed, and other parties can still upload data from that machine. A leecher will service the four fastest uploaders and choke the rest. Once the file has been completely downloaded, the client is considered a seed until the connection to the other peers is stopped and that peer is removed from the users' BitTorrent program, in practice by subtracting from the user the informative file detained by the tracker and by no longer showing this file as available for a certain file downloading.
The effectiveness of this data exchange mechanism depends largely on the policies that clients use to determine to whom data must be sent. Clients may prefer to send data to peers that send data back to them (a “tit for tat” scheme), which encourages fair trading. But excessively strict policies often result in suboptimal situations: for example, newly joined peers may be unable to receive data because they do not have any pieces to trade, or two peers having a good mutual connection may not exchange data simply because neither of them takes the initiative. In order to counter these effects, an official BitTorrent client program uses a mechanism known as “optimistic unchocking”, whereby the client reserves a portion of its available bandwidth for sending pieces to random peers (not necessarily known as good partners, the latter being called preferred peers) in the hope of discovering even better partners and to guarantee to the newcomers a chance to join the swarm.
In the general context of numeric communication, techniques are also known which bear the name of FEC (Forward Error Correction). In order to protect the data sent from a source to a receiver, FEC technologies involve encoding algorithms that add to the source data some degree of redundancy, i.e. additional repair data, in forming the encoded data. The decoding algorithm complementing a specific encoding algorithm allows the receiver to detect and in case to correct errors in the received data, solely on the basis of the received encoded data. The error correction action is “forward” in the sense that no feedback from the receiver to the sender or further transmission by the source are required. The additional redundancy introduced by FEC techniques implies that more information than just the original data is transmitted, resulting either in a longer transmission time (if the data rate is kept constant) or in a faster data rate and therefore in higher bandwidth occupancy (if the transmission time is kept constant).
Paradoxically, however, the additional redundancy can ultimately save transmission time and bandwidth use, if one considers the possible retransmissions that would be necessary without FEC. In applying FEC techniques, a basic tradeoff is achieved between the degree of error protection provided by a particular algorithm, the processing work involved by encoding and decoding, the introduced latency and/or overhead, and the bandwidth expansion necessary to protect against errors and data loss.
FEC techniques generally comprise error detection codes, error correction codes and erasure correction codes, adapted to meet different needs. Error detection codes allow the receiver to determine whether the received data are in error, but in general do not provide the means to identify and correct the errors. For example, a 1's complement checksum error detection code is used as a part of IP data packets to allow the receiver in order to check the integrity of the IP header and in TCP (Transport Control Protocol) and UDP (Unit Data Protocol) data packets in order to check the integrity of the header and of payload data.
Error correction codes allow the receiver to identify and correct up to a certain number of errors, occurring in the received data. For example, conventional or block error correction codes are used in the physical layers of 802.11a/b/g Wi-Fi devices and DOCSIS cable modems, in order to compensate for the bit error rates associated with those channels.
Erasure correction codes allow the receiver to correct up to a certain amount of missing data, when the positions of the missing data within the received data are already known. For example, Raptor code can be used in any packet data network in order to recover packets that have been “lost” either because they were never received or because errors were detected and the packets were discarded.
In a packet data network, packet loss is generally due to two reasons. First, the packets may have been discarded along the transmission path, for example because of a network congestion due to heavy traffic. Second, the data corruption may be such that any bit-level error correction code that might be used by the physical or link layer cannot restore the full packet, which is actually lost.
As an erasure correction code, Raptor can be used to provide packet-level protection at the transport layer or higher, increasing the bit-level protection that may be provided by the protocols at physical connection layer and by the use of error detection or error correction codes.
The erasure correction is particularly meaningful when the transport layer is not adapted to guarantee the packet delivery. A protocol such as TCP guarantees the delivery by implementing the mechanism known as ARQ (Automatic Repeat Request), based on timeouts and acknowledgements (ACK). However, the timeouts and round-trip-times (RTT) involved in the ARQ and ACK messages add on delay during the file download.
It is therefore very expensive to manage TCP connections, because connections are set up slowly and operating systems usually allow only for a limited number of TCP connections which, if the peer is unlucky, may refer to multiple slow or congested peers.
On the contrary, a UDP protocol does not guarantee the packet delivery, because it is a best-effort protocol. There are no timeouts or ARQ/ACK messages. The protocol is therefore very light and fast, and this is the reason why it is used in low-latency applications, such as streaming and VoIP.
UDP is a connection-less protocol, wherein the exchange of data between source and receiver (or receivers) does not require the preventive creation of a circuit, either physical or virtual, over which the whole data flow is directed, in a predetermined and sequential order.
UDP connections are set up quickly, and many connections may be active at a given time; as a consequence, within this set of connections there may be a sub-set of fast peers which can help downloading the file very quickly.
The UDP protocol does not manage the reordering of packets or the retransmission of lost packets, and therefore it is generally considered as less reliable. UDP provides basic services at transport layer, i.e. connection multiplexing through a gate mechanism, and error check through a checksum, inserted in a field of the packet heading.
The erasure recovery technology is useful to allow the implementation of many fast and light UDP connections, enabling the peers to download at the fastest possible speed.
Another aspect, which is still debated in literature, concerns whether it is preferable to adopt a “push” approach, wherein peers are suggested to send data without waiting for specific requests. In a well-known and stable tree-structure delivery network, it is possible to reduce the amount of overhead messages which communicate what to download. The more stable the overlay is, the less the need is felt to have policy messages generating a complex and redundant overhead. It is possible to properly foresee the data chunks that peers will request in the near future, without having to send block requests; the supplier simply sends the blocks in order, therefore “pushing” data chunks into the overlay network.
On the other hand, if the overlay network is widely affected by a free riding behaviour, peers frequently look for new neighbours, so that it becomes advantageous to make individual peers more independent from one another in terms of global management. An excessively structured overlay network can be complicated to set up and time consuming if the overlay is frequently destroyed and rebuilt. The flexibility is obtained through an intense signalling message policy. This scenario leads designers to approach P2P applications in a “pull” fashion: the peer asks continuously to receive the content which he currently needs, therefore it retrieves or “pulls” data chunks from neighbours.
The push vs. pull approach is therefore to be evaluated by keeping in mind the need to have more or less overhead and the willingness to accept a lower robustness in comparison with the overlay network changes. Clearly, the optimal choice would be such as to get as much efficiency as robustness.
The techniques based on the codes known as fountain codes have been widely analyzed in literature, and they have been used in telecommunications. The relevant feature of such codes is the ability to retrieve the information from a sufficiently high number of randomly selected packets. This is possible because each chunk of information is spread over all chunks belonging to the same data unit.
Chunks are randomly X-ORed among themselves so that, after the reception of K+few chunks X-ORed with a moderate overhead of 1-2% additional chunks information, it is generally possible to recover the original information. It is substantially a flexible (as many random chunks as needed can be generated on the fly, there is no pre-defined code-rate) and low-complexity (no maths using Galois fields) Forward Error Correction (FEC) technology, that finds application in a streaming scenario, in a distributed file system storage space as well as in a distributed content delivery network, as is the case in P2P networks. In such a context, the technologies based on fountain code encoding can solve the problem of missing/lost blocks when the overlay is strongly affected by free riding behaviour because peers disconnect, change channels, turn off the machine/Set Top Box or, more simply, in case of network congestion.
In a standard Bit Torrent application, a specific data block is needed to complete a data piece. On the contrary, by using fountain code encoding, the system is more robust because it is possible to retrieve the information of a missing block by downloading any combination of blocks X-ORed with the missing one.
In a P2P environment, fountain code technology also addresses the issue of delayed blocks when the peers are slow or congested and/or the network is continuously congested. From this point of view, lost blocks are a special case of delayed blocks: a lost block is a block with infinite delay. By using DF encoding it is not necessary to wait for a specific block from a specific peer. On the contrary any block X-ORed with the delayed one will serve the purpose.
In this respect, the RAPTOR code, which represents the most widespread specific version of the DF encoding, is proprietor but its use has been granted for free after standardization c/o IETF. Other versions of DF are known as well, such as Random Digital Fountain codes, which make it possible to get almost the same performance as Digital Fountains, with a lower decoding complexity.
Objects related to what previously described are discussed for example in the documents “Digital Fountain Codes for Peer-to-Peer Networks” by Ruben Villa, available on the date of filing of the present application at the Internet address http://rubenlinovilla.googlepages.com/Digital fountain codes for P2P Netwo.pdf, and “Erasure Correcting Techniques for UDP and Peer-to-Peer System” by Noam Singer, available on the date of filing of the present application at the Internet address http://www.cs.bgu.ac.il/˜singern/ln/studies/research/thesis/NoamSingerThesis.pdf.